Definition

A function ff is convex iff for any 𝐱,𝐲,λ∈[0,1]\mathbf{x},\mathbf{y},\lambda \in [0,1]:

(1−λ)⋅f(𝐱)+λ⋅f(𝐲)≥f((1−λ)⋅𝐱+λ⋅𝐲)(1-\lambda) \cdot f(\mathbf{x})+\lambda \cdot f(\mathbf{y}) \geq f((1-\lambda) \cdot \mathbf{x} + \lambda \cdot \mathbf{y})

(see Jensen's inequality)

convexity in one dimension

A twice-differentiable function f:ℝ→Rf : \mathbb{R} → R is:

  • convex if and only if f′′(x)≥0f''(x) ≥ 0 for all xx.
  • β-smooth if f′′(x)≤βf''(x) ≤ β.
  • α-strongly convex if f′′(x)≥αf''(x) ≥ α.

Definition (function convexity, gradient)

A function ff is convex if and only if for any 𝐱,𝐲\mathbf{x},\mathbf{y}:

f(𝐱+𝐳)≥f(𝐱)+∇f(𝐱)𝖳𝗓f(\mathbf{x}+\mathbf{z}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^\mathsf{T} \sf{z}

equivalently,

f(𝐱)−f(𝐲)≤∇f(𝐱)𝖳(𝐱−𝐲)f(\mathbf{x}) - f(\mathbf{y}) \leq \nabla f(\mathbf{x})^\mathsf{T} (\mathbf{x}-\mathbf{y})

See also:

References:

  1. https://www.cs.cornell.edu/courses/cs6783/2018fa/lec16-supplement.pdf